#include <iostream>
//#include <stdio.h>
//2011年42题真题练习
//给两个长度相等，升序排列的数组，找出两个数组的中间点的值

int MidSearch(int* A,int* B,int len)
{
    int s1=0,d1=len-1,m1;  //定义数组的头下标和尾下标和中间结点
    int s2=0,d2=len-1,m2;

    while(s1!=d1 || s2!=d2)
    {
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(A[m1]== B[m2]){
            return A[m1];
        }
        if(A[m1] < B[m2]){
            if((s1+d1)%2==0){  //表示数组长度为奇数
                s1=m1;
                d2=m2;
            }
            else{  //数组长度为偶数
                s1=m1+1;
                d2=m2;
            }
        }
        else{
            if((s1+d1)%2==0){  //表示数组长度为奇数
                s2=m2;
                d1=m1;
            }
            else{  //数组长度为偶数
                s2=m2+1;
                d1=m1;
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];
}

int main() {
    int A[]={11,13,15,17,19,77};
    int B[]={2,4,6,8,20,22};
    int len=sizeof(A)/sizeof(int);
    int mid=MidSearch(A,B,len);
    printf("%d\n",mid);
    return 0;
}
